package com.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 935. 骑士拨号器 (中等)
 * <p>
 * 象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 L 的形状)。
 * 我们有一个象棋骑士和一个电话垫，如下所示，骑士只能站在一个数字单元格上(即蓝色单元格)。
 * 给定一个整数 n，返回我们可以拨多少个长度为 n 的不同电话号码。
 * 你可以将骑士放置在任何数字单元格上，然后你应该执行 n - 1 次移动来获得长度为 n 的号码。所有的跳跃应该是有效的骑士跳跃。
 * 因为答案可能很大，所以输出答案模 109 + 7.
 */
public class LeetCode935 {

    public static void main(String[] arg0) {
        int n = 3131;
        System.out.println("res = " + knightDialer(n));
    }

    /**
     * [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]
     * 如上，0只可能跳跃到4和6，如果接着跳，4只可能跳跃到0，3，9。6只可能跳跃到0，1，7。
     * 而5跳不到任何地方，任何地方也跳不到5。
     */
    public static int knightDialer(int n) {
        if (n == 1) {
            return 10;
        }

        Map<Integer, int[]> knightMap = new HashMap<>();
        knightMap.put(0, new int[]{4, 6});
        knightMap.put(1, new int[]{6, 8});
        knightMap.put(2, new int[]{7, 9});
        knightMap.put(3, new int[]{4, 8});
        knightMap.put(4, new int[]{0, 3, 9});
        knightMap.put(5, new int[]{});
        knightMap.put(6, new int[]{0, 1, 7});
        knightMap.put(7, new int[]{2, 6});
        knightMap.put(8, new int[]{1, 3});
        knightMap.put(9, new int[]{2, 4});

        long res = 0;
        // 记录n增加时[0-9]各个数字出现的次数
        long[] numCount = new long[10];
        Arrays.fill(numCount, 1);
        // 记录n增加时 数字次数 * 骑士跳跃结果数量，就是上面Map的值的长度，一般2个或者3个
        long[] numRes = new long[10];
        for (int i = 0; i < n - 1; i++) {
            long[] a = new long[10];
            for (int j = 0; j < 10; j++) {
                int[] curr = knightMap.get(j);
                if (i == (n - 2)) { // 只最后一次记录结果就行
                    numRes[j] = (long) (numCount[j] * curr.length % (1E9 + 7));
                }
                for (int k = 0; k < curr.length; k++) {
                    int num = curr[k];
                    a[num] += numCount[j];
                    // 次数会变的很大，最后会都变成0，次数之后都会乘以一个整数，所以可以先取余
                    a[num] = (long) (a[num] % (1E9 + 7));
                }
            }
            System.out.println("a = " + Arrays.toString(a));
            numCount = a;
        }

        System.out.println("numRes = " + Arrays.toString(numRes));
        for (int i = 0; i < numRes.length; i++) {
            res += numRes[i];
        }

        return (int) (res % (1E9 + 7));
    }

}
